package dynamic_array;

import java.util.Arrays;

/**
 * 基于int的动态数组，根据元素的个数动态调整数组大小
 */
public class MyArray {
    //存放的元素仍然是int[]
    private int[] arr;
    //表示当前数组存放的有效元素
    private int size;

    public MyArray(){
        //也可以默认开辟长度为10的数组
        this(10);
    }

    public MyArray( int initCap){
        //可以由用户定义数组的长度
        this.arr=new int[initCap];
    }



    /**
     * 删除所有值为val的元素
     * @param val
     * @return
     */
    public int removeAllVal(int val){
        //k用来记录数组中与等于val的元素
       int k=0;
        for (int i = 0; i < arr.length; i++) {
            //此时如果元素等于val，则k++
            if (arr[i]==val){
                k++;
            }else{
                //此时如果元素不等于val，就将当前元素向前移动k个位置，就相当于删除了k个与val相同的元素
                arr[i-k]=arr[i];
            }
        }size-=k;//重新定义有效元素个数

        return k;     //返回数组中和val相同元素的个数
    }

    /**
     * 删除第一个值为val的元素，删除成功返回true
     * @param val
     * @return
     */
    public boolean removeByValFirst(int val){
        for (int i = 0; i <size-1; i++) {
            if (arr[i]==val){
                //此时找到了第一个值为val的元素
                remove(i);
                return true;
            }
        }return false;
    }

    /**
     * 删除第一个元素
     * @return
     */
    public int removeFirst(){
        return remove(0);
    }

    /**
     * 删除最后一个元素
     * @return
     */
    public int removeLast(){
        return remove(size-1);
    }



    /**
     * 删除索引为index所对应的元素，返回删除前的元素值
     * @param index
     * @return
     */
    public int remove(int index){
        if (index<0||index>=size){
            System.out.println("index不在范围内");
        }
        //进行元素搬移，从index开始，后一个元素覆盖前一个元素，一直到size-1（即为最后一个有效元素）
        int oldVal=arr[index];
        for (int i = index; i <size-1; i++) {

            arr[i]=arr[i+1];

        }size--;
        //返回修改前的值
        return oldVal;

    }


    /**
     * 修改第一个值为oldVal的元素为newVal,修改成功返回true，反之返回false
     * @param oldVal
     * @param newVal
     * @return
     */
    public boolean setVal(int oldVal,int newVal){
        int index=getByValue(oldVal);
        if (index!=-1){
            arr[index]=newVal;
            return true;
        }
        System.out.println("oldVal不存在");
        return false;
    }


    /**
     * 修改index位置的元素为新的元素newVal,并且返回修改前的值
     * @param index
     * @param newVal
     * @return
     */
    public int set(int index,int newVal){
        if (index<0||index>=size){
            System.out.println("index不在范围内");
        }
        int oldVal=arr[index];
        arr[index]=newVal;
        //返回修改前的值
        return oldVal;
    }


    /**
     * 在当前动态数组的index位置添加元素val
     * @param index
     * @param val
     */
    public void add(int index,int val){
        //首先判断边界条件，判断index是否在范围内
        //当index==size时，就相当于在数组的末尾插入，index==0就是在数组的头部插入
        if (index<0||index>size){
            System.err.println("index不在范围内");
            return;
        }
        for (int i = size-1; i >=index; i--) {
            arr[i+1]=arr[i];
        }
        arr[index]=val;
        size++;
        //判断数组是否已满
        if (size== arr.length){
            grow();
        }
    }

    /**
     * 查询数组中索引为index的元素值
     * @param index
     * @return
     */
    public int get(int index){
        if (index<0||index>=size){
            System.err.println("index不在范围内");
            return -1;
        }
        return arr[index];
    }

    /**
     * 查询数组中是否包含值为val的元素，存在时返回true，反之false
     * @return
     */
    public boolean contains(int val){
       int index=getByValue(val);
       return index!=-1;
    }

    /**
     * 查询当前数组中的第一个值为val的元素对应的索引,若不存在则返回-1
     * @param val
     * @return
     */
    public int getByValue(int val){
        //遍历数组，寻找元素val
        for (int i = 0; i <size; i++) {
            if (arr[i]==val){
                return i;
            }
            //此时遍历完毕，仍没有找到，返回-1
        }return -1;
    }

    /**
     * 在当前数组添，加一个新元素val，默认为数组末尾
     * @param val
     */
    public void add(int val){
        arr[size]=val;
        size++;
        //在添加数字时，如果size==arr.length，此时表名数组已满
        if (size== arr.length){
            grow();
        }
    }

    private void grow() {
        //copyOf方法返回了扩容后的新数组
       this.arr= Arrays.copyOf(arr,arr.length*2);
    }
    public String toString(){
        String ret="[";
        //此时取到的是有效数据，需要size来判断
        for (int i = 0; i <size; i++) {
            ret+=arr[i];
            if (i!=size-1){
                ret+=", ";
            }
        }ret+="]";
        return ret;
    }
}
